import java.util.*;

class BinaryTreeNode{

	private int data;
	private int weight;
	BinaryTreeNode left;
	BinaryTreeNode right;

	void setData(int data)
	{
		this.data = data;
	}

	int getData()
	{
		return(data);
	}

	void setWeight(int weight)
	{
		this.weight = weight;
	}

	int getWeight()
	{
		return(weight);
	}

	void setLeft(BinaryTreeNode left)
	{
		this.left = left;
	}

	BinaryTreeNode getLeft()
	{
		return(left);
	}

	void setRight(BinaryTreeNode right)
	{
		this.right = right;
	}

	BinaryTreeNode getRight()
	{
		return(right);
	}
	
}

public class BinaryTree {

static BinaryTreeNode root;

public BinaryTree(int data)
{
	root = new BinaryTreeNode();
	root.setData(data);
	root.setLeft(null);
	root.setRight(null);
	root.setWeight(0);
}

public BinaryTree(int data,int weight)
{
	root = new BinaryTreeNode();
	root.setData(data);
	root.setLeft(null);
	root.setRight(null);
	root.setWeight(weight);
}

BinaryTreeNode insert(int data)
{
	BinaryTreeNode node = new BinaryTreeNode();
	node.setData(data);
	node.setLeft(null);
	node.setRight(null);
	node.setWeight(0);
	return node;
}


BinaryTreeNode insert(int data,int weight)
{
	BinaryTreeNode node = new BinaryTreeNode();
	node.setData(data);
	node.setLeft(null);
	node.setRight(null);
	node.setWeight(weight);
	return node;
}

void LevelOrderTraversal(BinaryTreeNode root)
{
	BinaryTreeNode temp;
	if(root == null)
		return;
	Queue<BinaryTreeNode> q = new LinkedList<BinaryTreeNode>();
	q.add(root);

	Iterator iter = q.iterator();
	while(!q.isEmpty())
	{
		temp = q.poll();
		System.out.print(temp.getData()+" ");

		if(temp.getLeft()!=null)
			q.offer(temp.getLeft());
		if(temp.getRight()!=null)
			q.offer(temp.getRight());

	}
}

void preOrderTraversal(BinaryTreeNode root)
{
	if(root == null) return;
	System.out.print(root.getData()+" ");
	preOrderTraversal(root.getLeft());
	preOrderTraversal(root.getRight());
}

void postOrderTraversalIterative2Stacks(BinaryTreeNode root)
{
	if(root==null) return;
	Stack S1 = new Stack();
	Stack S2 = new Stack();

	S1.push(root);

	while(!S1.isEmpty())
	{
		BinaryTreeNode temp = (BinaryTreeNode)S1.pop();
		S2.push(temp);
		if(temp.getLeft()!=null)
			S1.push(temp.getLeft());
		if(temp.getRight()!=null)
			S1.push(temp.getRight());

	}
	System.out.println();
	while(!S2.isEmpty())
	{

		System.out.print(((BinaryTreeNode)S2.pop()).getData()+" ");
	}
}


int getNextRight(BinaryTreeNode root, int key){

	ArrayList<BinaryTreeNode> treeArray = new ArrayList<BinaryTreeNode>();
	BinaryTreeNode temp;
	if(root == null)
		return -1;
	Queue<BinaryTreeNode> q = new LinkedList<BinaryTreeNode>();
	q.add(root);
	q.add(null);
	Iterator iter = q.iterator();
	while(!q.isEmpty())
	{
		temp = q.poll();
		treeArray.add(temp);
		//System.out.print(temp.getData()+" ");
		if(temp==null)
		{
			if(!q.isEmpty())
				q.offer(null);
		}

		if(temp!=null && temp.getLeft()!=null)
			q.offer(temp.getLeft());
		if(temp!=null && temp.getRight()!=null)
			q.offer(temp.getRight());

	}
	int i = 0;
	for(BinaryTreeNode b: treeArray)
	{

		if(b!=null && b.getData() == key)
		{
			if(i+1 < treeArray.size() && treeArray.get(i+1)!=null)
			return(treeArray.get(i+1).getData());
			else
				return(-1);
		}
		i++;		
	}

	return(-1);




}
void postOrderTraversalIterative1Stack(BinaryTreeNode root)
{
	Stack S = new Stack();
	while(true)
	{
		if(root!=null)
		{
			S.push(root);
			root = root.getLeft();
		}

		else
		{
			if(S.isEmpty())
			{
				System.out.println("Stack is empty");
				return;
			}
			if(((BinaryTreeNode)S.peek()).getRight()==null)
			{
				root = (BinaryTreeNode)S.pop();
				System.out.print(root.getData());

				if(root == ((BinaryTreeNode)S.peek()).getRight() && !S.isEmpty())
				{
					System.out.println(((BinaryTreeNode)S.peek()).getData());
					S.pop();
				}
				if(!S.isEmpty()) root= ((BinaryTreeNode)S.peek()).getRight();
				else root = null;
			}
		}
	}
	
}
static Set<Integer> S = new HashSet<Integer>();
int maxweight(BinaryTreeNode node)
{
	if(node==null)
		return 0;
	if(node.getWeight() > (maxweight(node.getLeft())+maxweight(node.getRight())))
	{
		//S.push(node);
		S.add(node.getWeight());
		return node.getWeight();
	}
	else

		return (maxweight(node.getLeft())+maxweight(node.getRight()));
}

public static void main(String[] args) {
	/*BinaryTree bt = new BinaryTree(1);
	root.setLeft(bt.insert(2));
	root.setRight(bt.insert(3));
	root.getLeft().setLeft(bt.insert(4));
	root.getLeft().setRight(bt.insert(5));
	root.getRight().setLeft(bt.insert(6));
	root.getRight().setRight(bt.insert(7));*/
	
    /*BinaryTree bt = new BinaryTree(10);
	root.setLeft(bt.insert(2));
	root.setRight(bt.insert(6));
	root.getLeft().setLeft(bt.insert(8));
	root.getLeft().setRight(bt.insert(4));
	root.getLeft().getRight().setRight(bt.insert(9));
	root.getRight().setLeft(bt.insert(7));
	root.getRight().setRight(bt.insert(5));*/


	BinaryTree bt = new BinaryTree(1,1);
	root.setLeft(bt.insert(2,2));
	root.setRight(bt.insert(3,3));
	root.getLeft().setLeft(bt.insert(4,4));
	root.getLeft().setRight(bt.insert(5,5));
	root.getRight().setRight(bt.insert(6,6));
	root.getRight().getRight().setRight(bt.insert(7,100));

	/*System.out.println("----------LevelOrderTraversal----------");
	System.out.println();
	bt.LevelOrderTraversal(bt.root);
	System.out.println();
	//bt.preOrderTraversal(bt.root);
	//bt.postOrderTraversalIterative2Stacks(bt.root);
	//bt.postOrderTraversalIterative1Stack(bt.root);
	System.out.println(bt.getNextRight(bt.root,10));*/

	System.out.println(bt.maxweight(bt.root));
	System.out.println(S);

}

}